package chan.project.utils.routeTemplate;

import java.util.*;

/**
 * 记录终点与起点的最短路径算法
 */
public class DijkstraRouteTemplate extends RouteTemplate{
    /**
     * 暴力解法
     * @param graph
     * @return
     */
    @Override
    public Result minRoute(int[][] graph) {
        int n = graph.length;
        int[][] dp = new int[1 << n][n];
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dp[1][0] = 0;
        int[][] parent = new int[1 << n][n];
        for (int mask = 1; mask < (1 << n); mask++) {
            for (int u = 0; u < n; u++) {
                if ((mask & (1 << u)) != 0) {
                    for (int v = 0; v < n; v++) {
                        if (v != 0 && (mask & (1 << v)) == 0) {
                            int newMask = mask | (1 << v);
                            if (dp[mask][u] != Integer.MAX_VALUE && graph[u][v] != 0) {
                                if (dp[newMask][v] > dp[mask][u] + graph[u][v]) {
                                    dp[newMask][v] = dp[mask][u] + graph[u][v];
                                    parent[newMask][v] = u;
                                }
                            }
                        }
                    }
                }
            }
        }
        int finalMask = (1 << n) - 1;
        int minCost = dp[finalMask][n-1];
        int endNode = n-1;

        if(minCost == Integer.MAX_VALUE) {
            return new Result(0, new int[0]); // No path found
        }

        int[] path = new int[n];
        int currentMask = finalMask;
        int currentNode = endNode;
        for (int i = n - 1; i >= 0; i--) {
            path[i] = currentNode;
            int parentNode = parent[currentMask][currentNode];
            currentMask = currentMask ^ (1 << currentNode);
            currentNode = parentNode;
        }
        return new Result(minCost, path);
    }
}
